#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
using namespace std;


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if (root == nullptr)
    {
        return ret;
    }
    queue<TreeNode*> q;
    q.push(root);
    int tag = 1;
    while (!q.empty())
    {
        vector<int> v;
        int sz = q.size();
        for (int i = 0; i < sz; i++)
        {
            TreeNode* node = q.front();
            q.pop();
            v.push_back(node->val);
            if (node->left != nullptr)
            {
                q.push(node->left);
            }
            if (node->right != nullptr)
            {
                q.push(node->right);
            }
        }
        if (tag % 2 == 0)
        {
            reverse(v.begin(), v.end());
        }
        tag++;
        ret.push_back(v);
    }
    return ret;
}


int main()
{
    return 0;
}